'''
https://leetcode.cn/problems/maximum-profit-in-job-scheduling/
'''
import bisect
from functools import cache
from typing import List
class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
        @cache
        def f(i):
            if i == n:
                return 0
            p1 = f(i+1)
            p2 = jobs[i][2]
            # 只能选择，比开始时间 <= 我当前的时间的工作
            j = bisect.bisect_left(jobs, jobs[i][1], key=lambda x: x[0])
            p2 += f(j)
            return max(p1, p2)
        return f(0)

    def jobScheduling2(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[0])
        dp = [0] * (n+1)
        for i in range(n-1, -1, -1):
            p1 = dp[i+1]
            j = bisect.bisect_left(jobs, jobs[i][1], key=lambda x: x[0])
            p2 = jobs[i][2]
            p2 += dp[j]
            dp[i] = max(p1, p2)
        return dp[0]


startTime = [1,2,3,3]
endTime = [3,4,5,6]
profit = [50,10,40,70]
print(Solution().jobScheduling(startTime, endTime, profit))